package core;

//import staspecial.Edge;
import static special.Edge.*;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Stack;
import special.Edge;
import special.Flower;
import special.TreeNode;
import util.Pair;
import static util.Auxiliary.*;

/**
 *
 * @author Grega
 */
public class Edmonds
{
  // number of vertexes in graph
  final Integer sizeV;
  // edge-weight table
  final Double[][] edgeTable;
  // for each vertex there is vertex dependency (final number of vertexes)
  Stack<Flower>[] vertexDependency;
  // M contains every edge, which is selected in perfect matching
  HashSet<Pair> M;
  // every free tree in forest
  LinkedList<TreeNode> F;
  // every 2-Flower tree in forest
  LinkedList<TreeNode> F2;
  // change(r, T) -- every outermost flower moat in tree T changes +/- r
  double r;

  public Edmonds(Double[][] edgeTable)
  {
    this.edgeTable = edgeTable;
    this.sizeV = edgeTable.length;
    vertexDependency = new Stack[edgeTable.length];
    M = new HashSet<Pair>();
    F = new LinkedList<TreeNode>();
    F2 = new LinkedList<TreeNode>();
  }

  public void algorithm()
  {
    while (!isPerfectMatching(sizeV, M)) {
      // finds r
    }
  }

  // returns edge e with lowest weight - \sum(B_i.weight),
  // where e \in delta(B_i) for all i
  // returns outermost flower f in T with lowest moat width
  TreeNode emptiestFlower;
  Pair lowestFreeWeightPair;
  double lowestFreeWeight;
  HashSet<Integer> evenDepthV;
  HashSet<Integer> oddDepthV;

  public boolean lowestR(TreeNode treeNode)
  {
    lowestFreeWeight = Double.POSITIVE_INFINITY;
    evenDepthV = treeNode.getVInTree(true);
    oddDepthV = treeNode.getVInTree(false);
    return recursiveLowestR(treeNode);
  }

  public boolean recursiveLowestR(TreeNode treeNode)
  {
    boolean lowestOnEvenLevel = false; //this inicialization must be overriden

    if (!treeNode.children.isEmpty()) {
      for (int i = 0; i < treeNode.children.size(); i++) {
        lowestOnEvenLevel = recursiveLowestR(treeNode.children.get(i).connectedTo);
      }
    }

    if (treeNode.depth % 2 == 0) {
      HashSet<Integer> flowerV = treeNode.flower.vertexSet;
      Iterator<Integer> it = flowerV.iterator();

      HashSet<Integer> collisionV = fillWithInt(sizeV);
      collisionV.removeAll(flowerV);
      collisionV.removeAll(oddDepthV);

      while (it.hasNext()) {
        Integer v = it.next();
        Iterator<Integer> collisionVIt = collisionV.iterator();

        while (collisionVIt.hasNext()) {
          if (checkLowestWeight(new Pair(v, collisionVIt.next()))) {
            lowestOnEvenLevel = true;
          }
        }
      }
    } else {
      if (treeNode.flower.width < lowestFreeWeight) {
        emptiestFlower = treeNode;
        lowestFreeWeight = treeNode.flower.width;
        lowestOnEvenLevel = false;
      }
    }

    return lowestOnEvenLevel;
  }

  
  public void caseA()
  {
    TreeNode n = emptiestFlower;
    Pair p, ch;
    p = n.parent.label;
    // on this level it should be exactly one child
    ch = n.children.get(0).label;

    Integer vP, vCh;
    if (n.flower.vertexSet.contains(p.v1)) {
      vP = p.v1;
    } else {
      vP = p.v2; // we assume, that one of the vertexes is contained in flower
    }
    if (n.flower.vertexSet.contains(ch.v1)) {
      vCh = ch.v1;
    } else {
      vCh = ch.v2; // we assume, that one of the vertexes is contained in flower
    }
    
    Flower fP, fCh;
    // we assume, that small bubble won't be shrinked to 0, so we can access
    // bubble on lower level
    fP = vertexDependency[vP].get(vertexDependency[vP].size()-2);
    fCh = vertexDependency[vCh].get(vertexDependency[vCh].size()-2);

    TreeNode currentTN;
    Flower currentF;
    
    // because path is alternating, this will be our condition for next flower
    boolean isInM = true;

    currentTN = n.parent.connectedTo.addChild(fP, n.parent.label);
    currentF = currentTN.flower; // treeNode with flower fP

    while (currentTN.flower != fCh) {
      if (M.contains(currentTN.flower.left.label)==isInM) {
        currentTN = currentTN.addChild(currentTN.flower.left.connectedTo,
                currentTN.flower.left.label);
      } else {
        currentTN = currentTN.addChild(currentTN.flower.right.connectedTo,
                currentTN.flower.right.label);
      }
      isInM = !isInM;
    }

    currentTN.addChild(n.children.get(0));
    isInM = false;
    TreeNode f2Component;

    while (currentF != fCh) {
      if (M.contains(currentF.left.label)==isInM) {
        if (isInM) {
          f2Component = new TreeNode(currentF);
          f2Component.parent =
                  new Edge<TreeNode>(new TreeNode(currentF.left.connectedTo),
                                                  currentF.left.label);
          f2Component.parent.connectedTo.parent = new Edge<TreeNode>(f2Component,
                  currentF.left.label);
          F2.add(f2Component);
        }
        currentF = currentF.left.connectedTo;
      } else {
        if (isInM) {
          f2Component = new TreeNode(currentF);
          f2Component.parent =
                  new Edge<TreeNode>(new TreeNode(currentF.right.connectedTo),
                                                  currentF.right.label);
          f2Component.parent.connectedTo.parent = new Edge<TreeNode>(f2Component,
                  currentF.right.label);
          F2.add(f2Component);
        }
        currentF = currentF.right.connectedTo;
      }
    }
  }

  // ensure, you have correctly initialized and filled all used global variables
  // checks lowest weight reached on even
  // returns true iff lowest weight was adapted
  private boolean checkLowestWeight(Pair p)
  {
    double freeWeight = freeWeight(edgeTable[p.v1][p.v2],
            vertexDependency[p.v1], vertexDependency[p.v2]);

    if (evenDepthV.contains(p.v1) && evenDepthV.contains(p.v2)) {
      freeWeight = freeWeight / 2;
    }
    if (lowestFreeWeight > freeWeight) {
      lowestFreeWeight = freeWeight;
      lowestFreeWeightPair = p;
      return true;
    }
    return false;
  }

}
